package primaryAlgorithm.shuffleArray;

import java.util.Random;

/**
 * @Date 2020/03/24
 * @author 王光浩
 * @Thinking 在上一个方法中，我们的时间复杂度为O（n^2）主要原因是当我们随机道一个元素后，需要将这个元素删除，
 * @         这需要O（n）的时间复杂度，但是如果我们讲两个元素交换，就可以免去这个O（n）的开销。注意元素必须能够和它
 * @         本身进行交换，否则概率将会不对。
 */
public class MyMethodThree {
	private int[] original;
	private int[] shulle;
	private Random random=new Random();
	public MyMethodThree(int[] nums) {
		original=nums;
		shulle=new int[nums.length];
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
    	return original;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	for(int i=0;i<original.length;i++){
    		shulle[i]=original[i];
    	}
    	for(int i=original.length-1;i>=0;i--) {
    		int tem=random.nextInt(i);
    		if(tem==i)continue;
    		shulle[i]=shulle[i]^shulle[tem];
    		shulle[tem]=shulle[i]^shulle[tem];
    		shulle[i]=shulle[i]^shulle[tem];
    	}
    	return shulle;
    }
}
